package com.exercises;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Exercise39 {
    public static void main(String[] args) {
        int[] candidates = new int[]{2, 3, 6, 7};
//        for (int i = 0; i < candidates.length; i++) {
//            for (int a : Arrays.copyOf(candidates, i)) {
//                System.out.print(a + " ");
//            }
//            System.out.println();
//        }
        int target = 7;
        List<List<Integer>> result = new Exercise39().combinationSum(candidates, target);
        result.forEach(l -> {
            for (Integer i : l) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        });
    }


    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        if (candidates.length == 0 || candidates[0] > target) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < candidates.length; i++) {
            int value = candidates[i];
            if (value < target) {
                List<List<Integer>> temp = combinationSum(Arrays.copyOfRange(candidates, i, candidates.length), target - value);
                if (temp.size() != 0) {
                    temp.forEach(t -> t.add(value));
                    result.addAll(temp);
                }
            } else if (value == target) {
                List<Integer> a = new ArrayList<>();
                a.add(value);
                List<List<Integer>> b = new ArrayList<>();
                b.add(a);
                result.addAll(b);
            } else {
                break;
            }
        }

        return result;
    }
}
